{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Resultant Array After Removing Anagrams"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeAnagrams"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移除字母异位词后的结果数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的字符串 <code>words</code> ，其中 <code>words[i]</code> 由小写英文字符组成。</p>\n",
    "\n",
    "<p>在一步操作中，需要选出任一下标 <code>i</code> ，从 <code>words</code> 中 <strong>删除</strong> <code>words[i]</code> 。其中下标 <code>i</code> 需要同时满足下述两个条件：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>0 &lt; i &lt; words.length</code></li>\n",
    "\t<li><code>words[i - 1]</code> 和 <code>words[i]</code> 是 <strong>字母异位词</strong> 。</li>\n",
    "</ol>\n",
    "\n",
    "<p>只要可以选出满足条件的下标，就一直执行这个操作。</p>\n",
    "\n",
    "<p>在执行所有操作后，返回 <code>words</code> 。可以证明，按任意顺序为每步操作选择下标都会得到相同的结果。</p>\n",
    "\n",
    "<p><strong>字母异位词</strong> 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。例如，<code>\"dacb\"</code> 是 <code>\"abdc\"</code> 的一个字母异位词。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>words = [\"abba\",\"baba\",\"bbaa\",\"cd\",\"cd\"]\n",
    "<strong>输出：</strong>[\"abba\",\"cd\"]\n",
    "<strong>解释：</strong>\n",
    "获取结果数组的方法之一是执行下述步骤：\n",
    "- 由于 words[2] = \"bbaa\" 和 words[1] = \"baba\" 是字母异位词，选择下标 2 并删除 words[2] 。\n",
    "  现在 words = [\"abba\",\"baba\",\"cd\",\"cd\"] 。\n",
    "- 由于 words[1] = \"baba\" 和 words[0] = \"abba\" 是字母异位词，选择下标 1 并删除 words[1] 。\n",
    "  现在 words = [\"abba\",\"cd\",\"cd\"] 。\n",
    "- 由于 words[2] = \"cd\" 和 words[1] = \"cd\" 是字母异位词，选择下标 2 并删除 words[2] 。\n",
    "  现在 words = [\"abba\",\"cd\"] 。\n",
    "无法再执行任何操作，所以 [\"abba\",\"cd\"] 是最终答案。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>words = [\"a\",\"b\",\"c\",\"d\",\"e\"]\n",
    "<strong>输出：</strong>[\"a\",\"b\",\"c\",\"d\",\"e\"]\n",
    "<strong>解释：</strong>\n",
    "words 中不存在互为字母异位词的两个相邻字符串，所以无需执行任何操作。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 10</code></li>\n",
    "\t<li><code>words[i]</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-resultant-array-after-removing-anagrams](https://leetcode.cn/problems/find-resultant-array-after-removing-anagrams/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-resultant-array-after-removing-anagrams](https://leetcode.cn/problems/find-resultant-array-after-removing-anagrams/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"abba\",\"baba\",\"bbaa\",\"cd\",\"cd\"]', '[\"a\",\"b\",\"c\",\"d\",\"e\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        st = []\n",
    "        for w in words:\n",
    "            cnt = Counter(w)\n",
    "            if st and st[-1][0] == cnt:\n",
    "                continue\n",
    "            else:\n",
    "                st.append((cnt, w))\n",
    "\n",
    "        return [x[1] for x in st]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = [words[0]]   # 结果数组\n",
    "        n = len(words)\n",
    "        # 判断两个单词是否为字母异位词\n",
    "        def compare(word1: str, word2: str) -> bool:\n",
    "            freq = [0] * 26\n",
    "            for ch in word1:\n",
    "                freq[ord(ch)-ord('a')] += 1\n",
    "            for ch in word2:\n",
    "                freq[ord(ch)-ord('a')] -= 1\n",
    "            return all(x == 0 for x in freq)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if compare(words[i], words[i-1]):\n",
    "                continue\n",
    "            res.append(words[i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        n, i, j = len(words), 0, 1\n",
    "        ans = []\n",
    "        while j < n:\n",
    "            if sorted(words[i]) != sorted(words[j]):\n",
    "                ans.append(words[i])\n",
    "                i = j\n",
    "            j += 1\n",
    "        ans.append(words[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        for i in range(len(words)-1,-1,-1):            \n",
    "            if i-1>=0 and words[i]!=None:\n",
    "                l=list(words[i])\n",
    "                l.sort()\n",
    "                m=list(words[i-1])\n",
    "                m.sort()\n",
    "                if l==m:\n",
    "                    words[i]=None\n",
    "        for i in range(len(words)-1,-1,-1):\n",
    "            if words[i]==None:\n",
    "                words.pop(i)\n",
    "        return words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        def isAnagram(word1,word2):\n",
    "            if len(word1)!=len(word2):\n",
    "                return False\n",
    "            if set(word1)!=set(word2):\n",
    "                return False\n",
    "            counter=dict()\n",
    "            for i in range(len(word1)):\n",
    "                counter[word1[i]]=counter.get(word1[i],0)+1\n",
    "            for i in range(len(word2)):\n",
    "                counter[word2[i]]-=1\n",
    "            for key in counter:\n",
    "                if counter[key]!=0:\n",
    "                    return False\n",
    "            return True\n",
    "        size=len(words)\n",
    "        slow=0\n",
    "        fast=1\n",
    "        while fast<size:\n",
    "            if isAnagram(words[slow],words[fast]):\n",
    "                words[fast]=''\n",
    "            else:\n",
    "                slow=fast\n",
    "            fast+=1\n",
    "        ans=[]\n",
    "        for i in range(size):\n",
    "            if words[i]!='':\n",
    "                ans+=[words[i]]\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        # 构造判定字母异位词的函数, Counter() \n",
    "        # def check(s1:str, s2:str):\n",
    "        #     c1 = Counter(s1)\n",
    "        #     c2 = Counter(s2)\n",
    "        #     if c1 == c2:\n",
    "        #         return True\n",
    "        #     return False\n",
    "        # # 栈\n",
    "        # res = [words[0]]\n",
    "        # n = len(words)\n",
    "        # for i in range(1, n):\n",
    "        #     if not check(words[i], words[i-1]):\n",
    "        #         res.append(words[i])\n",
    "        # return res\n",
    "\n",
    "\n",
    "        # 双指针\n",
    "        # res = []\n",
    "        # n = len(words)\n",
    "        # i = 0\n",
    "        # while i < n:\n",
    "        #     j = i+1\n",
    "        #     while j < n and Counter(words[i]) == Counter(words[j]):\n",
    "        #         j += 1\n",
    "        #     res.append(words[i])\n",
    "        #     i = j\n",
    "        # return res\n",
    "\n",
    "\n",
    "        # 模拟\n",
    "        i = 1\n",
    "        while i < len(words):\n",
    "            # if sorted(words[i]) == sorted(words[i-1]):\n",
    "            if Counter(words[i]) == Counter(words[i-1]):\n",
    "                words.remove(words[i])\n",
    "            else:\n",
    "                i += 1\n",
    "        return words\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "      \n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = [words[0]]\n",
    "        n = len(words)\n",
    "        def compare(word1,word2):\n",
    "            freq = [0]*26\n",
    "            for ch in word1:\n",
    "                freq[ord(ch)-ord('a')] += 1\n",
    "            for ch in word2:\n",
    "                freq[ord(ch)-ord('a')] -= 1\n",
    "            return all(x==0 for x in freq)\n",
    "        for i in range(1,n):\n",
    "            if compare(words[i-1],words[i]):\n",
    "                continue\n",
    "            res.append(words[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        words2 = []\n",
    "        n = len(words)\n",
    "        pre = sorted(list(words[0]))\n",
    "        ret = [words[0]]\n",
    "        for i in range(1, n):\n",
    "            x = words[i]\n",
    "            y = list(x)\n",
    "            y.sort()\n",
    "            if y == pre:\n",
    "                continue\n",
    "            ret.append(words[i])\n",
    "            pre = y\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        # 字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次\n",
    "        while True:\n",
    "            for i in range(1,len(words)):\n",
    "                if sorted(words[i - 1]) == sorted(words[i]):\n",
    "                    words.remove(words[i])   # 这里会返回空，不能用变量去接收\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "        return words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        stack = []\n",
    "        for w in words:\n",
    "            if stack and Counter(w) == Counter(stack[-1]):\n",
    "                pass\n",
    "            else:\n",
    "                stack.append(w)\n",
    "        return stack\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        n = len(words)\n",
    "        idx = [True] * n\n",
    "        for i in range(1, n):\n",
    "            a = Counter(words[i])\n",
    "            b = Counter(words[i - 1])\n",
    "            if a == b:\n",
    "                idx[i] = False\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if idx[i]:\n",
    "                ans.append(words[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        for w in words:\n",
    "            if len(res) and sorted(res[-1]) == sorted(w):\n",
    "                continue\n",
    "            else:\n",
    "                res.append(w)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        hash_l = []\n",
    "        for i in words:\n",
    "            counter = Counter(i)\n",
    "            if not res:\n",
    "                hash_l.append(counter)\n",
    "                res.append(i)\n",
    "            elif counter != hash_l[-1]:\n",
    "                hash_l.append(counter)\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        n = len(words)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            j = i + 1\n",
    "            while j < n and Counter(words[i]) == Counter(words[j]):\n",
    "                j += 1\n",
    "            res.append(words[i])\n",
    "            i = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = [words[0]]   # 结果数组\n",
    "        n = len(words)\n",
    "        # 判断两个单词是否为字母异位词\n",
    "        def compare(word1: str, word2: str) -> bool:\n",
    "            freq = [0] * 26\n",
    "            for ch in word1:\n",
    "                freq[ord(ch)-ord('a')] += 1\n",
    "            for ch in word2:\n",
    "                freq[ord(ch)-ord('a')] -= 1\n",
    "            return all(x == 0 for x in freq)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if compare(words[i], words[i-1]):\n",
    "                continue\n",
    "            res.append(words[i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        tag = {}\n",
    "        for word in words:\n",
    "            w_count = {}\n",
    "            for w in word:\n",
    "                if w in w_count:\n",
    "                    w_count[w] += 1\n",
    "                else:\n",
    "                    w_count[w] = 1\n",
    "            tag[word] = w_count\n",
    "\n",
    "        def __check(w1, w2):\n",
    "            if len(w1) != len(w2):\n",
    "                return False\n",
    "            for k, v in tag[w1].items():\n",
    "                if k not in w2:\n",
    "                    return False\n",
    "                elif v != tag[w2][k]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        ans = [words[0]]\n",
    "        y = 1\n",
    "        while y < len(words):\n",
    "            if not __check(words[y], ans[-1]):\n",
    "                ans.append(words[y])\n",
    "            y += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        for i in words:\n",
    "            counter = Counter(i)\n",
    "            if not res:\n",
    "                res.append(i)\n",
    "            elif counter != Counter(res[-1]):\n",
    "                res.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = [words[0]]   # 结果数组\n",
    "        n = len(words)\n",
    "        # 判断两个单词是否为字母异位词\n",
    "        def compare(word1: str, word2: str) -> bool:\n",
    "            freq = [0] * 26\n",
    "            for ch in word1:\n",
    "                freq[ord(ch)-ord('a')] += 1\n",
    "            for ch in word2:\n",
    "                freq[ord(ch)-ord('a')] -= 1\n",
    "            return all(x == 0 for x in freq)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if compare(words[i], words[i-1]):\n",
    "                continue\n",
    "            res.append(words[i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        stk = []\n",
    "        for word in words:\n",
    "            if len(stk) == 0 or Counter(stk[-1]) != Counter(word):\n",
    "                stk.append(word)\n",
    "        return stk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        result = []\n",
    "        for word in words:\n",
    "            alive = True\n",
    "            if result!=[] and len(result[-1])==len(word):\n",
    "                for ascll in range(97,123):\n",
    "                    if word.count(chr(ascll))!=result[-1].count(chr(ascll)):\n",
    "                        break\n",
    "                else:\n",
    "                    alive=False\n",
    "            if alive:\n",
    "                result.append(word)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = [words[0]]   # 结果数组\n",
    "        n = len(words)\n",
    "        # 判断两个单词是否为字母异位词\n",
    "        def compare(word1: str, word2: str) -> bool:\n",
    "            freq = [0] * 26\n",
    "            for ch in word1:\n",
    "                freq[ord(ch)-ord('a')] += 1\n",
    "            for ch in word2:\n",
    "                freq[ord(ch)-ord('a')] -= 1\n",
    "            return all(x == 0 for x in freq)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if compare(words[i], words[i-1]):\n",
    "                continue\n",
    "            res.append(words[i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        n = len(words)\n",
    "\n",
    "        def compare(s1: str, s2: str) -> bool:\n",
    "            if len(s1) != len(s2):\n",
    "                return False\n",
    "            freq = [0] * 26\n",
    "            for j in s1:\n",
    "                freq[ord(j) - ord('a')] += 1\n",
    "            for j in s2:\n",
    "                freq[ord(j) - ord('a')] -= 1\n",
    "            return all(j == 0 for j in freq)\n",
    "\n",
    "        ans = [words[0]]\n",
    "        for i in range(1, n):\n",
    "            if not compare(words[i], words[i - 1]):\n",
    "                ans.append(words[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = [words[0]]   # 结果数组\n",
    "        n = len(words)\n",
    "        # 判断两个单词是否为字母异位词\n",
    "        def compare(word1: str, word2: str) -> bool:\n",
    "            freq = [0] * 26\n",
    "            for ch in word1:\n",
    "                freq[ord(ch)-ord('a')] += 1\n",
    "            for ch in word2:\n",
    "                freq[ord(ch)-ord('a')] -= 1\n",
    "            return all(x == 0 for x in freq)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if compare(words[i], words[i-1]):\n",
    "                continue\n",
    "            res.append(words[i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        st = []\n",
    "        for i, s in enumerate(words):\n",
    "            if st and Counter(s) == Counter(words[st[-1]]):\n",
    "              continue\n",
    "\n",
    "            st.append(i)  \n",
    "        \n",
    "        return [words[i] for i in st]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        hash_l = []\n",
    "        for i in words:\n",
    "            counter = Counter(i)\n",
    "            if not res:\n",
    "                hash_l.append(counter)\n",
    "                res.append(i)\n",
    "            elif counter != hash_l[-1]:\n",
    "                hash_l.append(counter)\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        n = len(words)\n",
    "        res = [words[0]]\n",
    "        flag = sorted(words[0])\n",
    "        for i in range(1,n):\n",
    "            if flag == sorted(words[i]):\n",
    "                continue\n",
    "            else:\n",
    "                res.append(words[i])\n",
    "                flag = sorted(words[i])\n",
    "            \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        i, j = 0, 1\n",
    "        ans = []\n",
    "        while j < len(words):\n",
    "            if Counter(words[j]) != Counter(words[i]):\n",
    "                ans.append(words[i])\n",
    "                i = j\n",
    "            j += 1\n",
    "        ans.append(words[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = [words[0]]   # 结果数组\n",
    "        n = len(words)\n",
    "        # 判断两个单词是否为字母异位词\n",
    "        def compare(word1: str, word2: str) -> bool:\n",
    "            freq = [0] * 26\n",
    "            for ch in word1:\n",
    "                freq[ord(ch)-ord('a')] += 1\n",
    "            for ch in word2:\n",
    "                freq[ord(ch)-ord('a')] -= 1\n",
    "            return all(x == 0 for x in freq)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if compare(words[i], words[i-1]):\n",
    "                continue\n",
    "            res.append(words[i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        \n",
    "        result = [words[0]]\n",
    "        temp = collections.Counter(words[0])\n",
    "        pos = 1\n",
    "        while pos < len(words):\n",
    "            if collections.Counter(words[pos]) != temp:\n",
    "                result.append(words[pos])\n",
    "                temp = collections.Counter(words[pos])\n",
    "\n",
    "            pos += 1\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = [words[0]]\n",
    "        for word in words[1:]:\n",
    "            if sorted(word) != sorted(res[-1]):\n",
    "                res.append(word)\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = [words[0]]   # 结果数组\n",
    "        n = len(words)\n",
    "        # 判断两个单词是否为字母异位词\n",
    "        def compare(word1: str, word2: str) -> bool:\n",
    "            freq = [0] * 26\n",
    "            for ch in word1:\n",
    "                freq[ord(ch)-ord('a')] += 1\n",
    "            for ch in word2:\n",
    "                freq[ord(ch)-ord('a')] -= 1\n",
    "            return all(x == 0 for x in freq)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if compare(words[i], words[i-1]):\n",
    "                continue\n",
    "            res.append(words[i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        n, i, j = len(words), 0, 1\n",
    "        ans = []\n",
    "        while j < n:\n",
    "            if Counter(words[j]) != Counter(words[i]):\n",
    "                ans.append(words[i])\n",
    "                i = j\n",
    "            j += 1\n",
    "        ans.append(words[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        i = 1\n",
    "        while i < len(words):\n",
    "            if Counter(words[i]) == Counter(words[i - 1]):\n",
    "                words.pop(i)\n",
    "            else:\n",
    "                i += 1\n",
    "        return words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        word_len = len(words)   # words = [\"abba\",\"baba\",\"bbaa\",\"cd\",\"cd\"]\n",
    "        z = []  # 存新的list\n",
    "        for i in range(word_len):\n",
    "            if i==0 or sorted(words[i])!=sorted(words[i-1]):    # 第一位不判断，Sorted排序判断是否一致\n",
    "                z.append(words[i])\n",
    "        return z\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]: \n",
    "        ans = [words[0]]\n",
    "        for i in range(1, len(words)):\n",
    "            if ''.join(sorted(words[i - 1])) == ''.join(sorted(words[i])):\n",
    "                continue\n",
    "            ans.append(words[i])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        stk = []\n",
    "        for word in words:\n",
    "            if len(stk) == 0 or Counter(stk[-1]) != Counter(word):\n",
    "                stk.append(word)\n",
    "        return stk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        n = len(words)\n",
    "\n",
    "        def helper(s1, s2):\n",
    "            return \"\".join(sorted(list(s1))) == \"\".join(sorted(list(s2)))\n",
    "\n",
    "        res = [words[0]]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if not helper(words[i], words[i - 1]):\n",
    "                res.append(words[i])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        de = []\n",
    "        for i in range(len(words)-1):\n",
    "            a = words[i]\n",
    "            b = words[i+1]\n",
    "            if sorted(a) == sorted(b):\n",
    "                de.append(b)\n",
    "        ret = []\n",
    "        for i in de:\n",
    "            words.remove(i)\n",
    "        return words\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        hash_l = []\n",
    "        for i in words:\n",
    "            counter = Counter(i)\n",
    "            if not res:\n",
    "                hash_l.append(counter)\n",
    "                res.append(i)\n",
    "            elif counter != hash_l[-1]:\n",
    "                hash_l.append(counter)\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        word_len = len(words)   # words = [\"abba\",\"baba\",\"bbaa\",\"cd\",\"cd\"]\n",
    "        z = []  # 存新的list\n",
    "        for i in range(word_len):\n",
    "            if i==0 or sorted(words[i])!=sorted(words[i-1]):    # 第一位不判断，Sorted排序判断是否一致\n",
    "                z.append(words[i])\n",
    "        return z\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        def check(a : string , b : string) -> bool :\n",
    "            return Counter(a) == Counter(b) \n",
    "        n = len(words)\n",
    "        ans = [words[0]]\n",
    "        for i in range(1,n) :\n",
    "            if not check(words[i-1] , words[i]) :\n",
    "                ans.append(words[i])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        x=0\n",
    "        y=1\n",
    "        while y<len(words):\n",
    "            if sorted(words[x])==sorted(words[y]):\n",
    "                words.remove(words[y])\n",
    "            else:\n",
    "                x+=1\n",
    "                y+=1\n",
    "        return words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        from collections import defaultdict, Counter\n",
    "        if len(words)<=1:\n",
    "            return words\n",
    "        slow, fast = 0,1\n",
    "        while fast<len(words):\n",
    "            if Counter(words[fast]) != Counter(words[slow]):\n",
    "                slow +=1\n",
    "                words[slow] = words[fast]\n",
    "            fast +=1\n",
    "        return words[:slow+1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        if False:\n",
    "            from collections import Counter\n",
    "            if not words:\n",
    "                return []\n",
    "\n",
    "            word_stack = []\n",
    "            for word in words:\n",
    "                if not word_stack:\n",
    "                    word_stack.append(word)\n",
    "                else:\n",
    "                    if Counter(word_stack[-1]) == Counter(word):\n",
    "                        continue\n",
    "                    else:\n",
    "                        word_stack.append(word)\n",
    "            return word_stack        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        pre = Counter()\n",
    "        prei = -1\n",
    "        for i, word in enumerate(words):\n",
    "            cur = Counter(word)\n",
    "            if cur == pre:\n",
    "                continue\n",
    "            else:\n",
    "                pre = cur\n",
    "                if prei != -1:\n",
    "                    ans.append(words[prei])\n",
    "                prei = i\n",
    "        ans.append(words[prei])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        \n",
    "        result = [words[0]]\n",
    "        temp = collections.Counter(words[0])\n",
    "        pos = 1\n",
    "        while pos < len(words):\n",
    "            if collections.Counter(words[pos]) != temp:\n",
    "                result.append(words[pos])\n",
    "                temp = collections.Counter(words[pos])\n",
    "\n",
    "            pos += 1\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = [words[0]]\n",
    "        n = len(words)\n",
    "        def compare(word1 : str , word2 : str) -> bool :\n",
    "            freq = [0] * 26 \n",
    "            for ch in word1:\n",
    "                freq[ord(ch) - ord('a')] += 1 \n",
    "            for ch in word2 :\n",
    "                freq[ord(ch)-ord('a')] -= 1 \n",
    "            return all(x == 0 for x in freq) \n",
    "        for i in range(1,n) :\n",
    "            if compare(words[i] , words[i-1]) :\n",
    "                continue \n",
    "            res.append(words[i])\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        from collections import defaultdict, Counter\n",
    "        if len(words)<=1:\n",
    "            return words\n",
    "        slow, fast = 0,1\n",
    "        while fast<len(words):\n",
    "            if Counter(words[fast]) != Counter(words[slow]):\n",
    "                slow +=1\n",
    "                words[slow] = words[fast]\n",
    "            fast +=1\n",
    "        return words[:slow+1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        if False:\n",
    "            from collections import Counter\n",
    "            if not words:\n",
    "                return []\n",
    "\n",
    "            word_stack = []\n",
    "            for word in words:\n",
    "                if not word_stack:\n",
    "                    word_stack.append(word)\n",
    "                else:\n",
    "                    if Counter(word_stack[-1]) == Counter(word):\n",
    "                        continue\n",
    "                    else:\n",
    "                        word_stack.append(word)\n",
    "            return word_stack        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res=[words[0]]\n",
    "        for i in range(1,len(words)):\n",
    "            p=list(res[-1])\n",
    "            q=list(words[i])\n",
    "            q.sort()\n",
    "            p.sort()\n",
    "            if q!=p:\n",
    "                res.append(words[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        hash_l = []\n",
    "        for i in words:\n",
    "            counter = Counter(i)\n",
    "            if not res:\n",
    "                hash_l.append(counter)\n",
    "                res.append(i)\n",
    "            elif counter != hash_l[-1]:\n",
    "                hash_l.append(counter)\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        hash_l = []\n",
    "        for i in words:\n",
    "            counter = Counter(i)\n",
    "            if not res:\n",
    "                hash_l.append(counter)\n",
    "                res.append(i)\n",
    "            elif counter != hash_l[-1]:\n",
    "                hash_l.append(counter)\n",
    "                res.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        dic=[words[0]]\n",
    "        i=1\n",
    "        while i<len(words):\n",
    "            li=list(words[i])\n",
    "            li.sort()\n",
    "            lj=list(words[i-1])\n",
    "            lj.sort()\n",
    "            if li != lj:\n",
    "                dic=dic+[words[i]]\n",
    "            i=i+1\n",
    "        return dic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = [words[0]]   # 结果数组\n",
    "        n = len(words)\n",
    "        # 判断两个单词是否为字母异位词\n",
    "        def compare(word1: str, word2: str) -> bool:\n",
    "            freq = [0] * 26\n",
    "            for ch in word1:\n",
    "                freq[ord(ch)-ord('a')] += 1\n",
    "            for ch in word2:\n",
    "                freq[ord(ch)-ord('a')] -= 1\n",
    "            return all(x == 0 for x in freq)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if compare(words[i], words[i-1]):\n",
    "                continue\n",
    "            res.append(words[i])\n",
    "        return res\n",
    " \n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        for i in words:\n",
    "            counter = Counter(i)\n",
    "            if not res:\n",
    "                res.append(i)\n",
    "            elif counter != Counter(res[-1]):\n",
    "                res.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        #判断是不是字母异位词，统计词频就可以了，如果是判断有没有公共的，可以做位运算(因为可以和1进行11对应，这种有多个的不太好)\n",
    "        stack=[]\n",
    "        for word in words:\n",
    "            cnt=[0]*26  \n",
    "            for s in word:\n",
    "                cnt[ord(s)-ord(\"a\")]+=1\n",
    "            #为了保持低空间复杂度，可以再取出栈顶元素然后再减一次（抵消操作）\n",
    "            if not stack:\n",
    "                stack.append(word)\n",
    "                continue\n",
    "            sk_word=stack[-1]\n",
    "            for s in sk_word:\n",
    "                cnt[ord(s)-ord(\"a\")]-=1\n",
    "            if cnt!=[0]*26:\n",
    "                stack.append(word)\n",
    "        return stack\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        \n",
    "        counterList = [Counter(x) for x in words]\n",
    "        ans = [words[0]]\n",
    "        last = counterList[0]\n",
    "\n",
    "        for i in range(1, len(words)):\n",
    "            if counterList[i] == last:\n",
    "                continue\n",
    "            ans.append(words[i])\n",
    "            last = counterList[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res = [words[0]]   # 结果数组\n",
    "        n = len(words)\n",
    "        # 判断两个单词是否为字母异位词\n",
    "        def compare(word1: str, word2: str) -> bool:\n",
    "            freq = [0] * 26\n",
    "            for ch in word1:\n",
    "                freq[ord(ch)-ord('a')] += 1\n",
    "            for ch in word2:\n",
    "                freq[ord(ch)-ord('a')] -= 1\n",
    "            return all(x == 0 for x in freq)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if compare(words[i], words[i-1]):\n",
    "                continue\n",
    "            res.append(words[i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        def judge(w1,w2):\n",
    "            return sorted(w1) == sorted(w2)\n",
    "        \n",
    "        ans,idx = [words[0]],0\n",
    "        for i in range(1,len(words)):\n",
    "            if not judge(words[idx],words[i]):\n",
    "                ans.append(words[i])\n",
    "                idx = i \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        ans=[words[0]]\n",
    "        for i in words:\n",
    "            a=sorted(list(ans[-1]))\n",
    "            b=sorted(list(i))\n",
    "            if a!=b:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        # 判断两个单词是否为字母异位词\n",
    "        def compare(word1: str, word2: str) -> bool:\n",
    "            freq = [0] * 26\n",
    "            for ch in word1:\n",
    "                freq[ord(ch)-ord('a')] += 1\n",
    "            for ch in word2:\n",
    "                freq[ord(ch)-ord('a')] -= 1\n",
    "            return all(x == 0 for x in freq)\n",
    "        res = [words[0]]\n",
    "        n = len(words)\n",
    "        for i in range(1, n):\n",
    "            if compare(words[i], words[i-1]):\n",
    "                continue\n",
    "            res.append(words[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        def compare(word1, word2) -> bool:\n",
    "            temp = [0] * 26\n",
    "            for ch in word1:\n",
    "                temp[ord(ch)-ord('a')] += 1\n",
    "            for ch in word2:\n",
    "                temp[ord(ch)-ord('a')] -= 1\n",
    "            return all(x == 0 for x in temp)\n",
    "        res = [words[0]]\n",
    "        n = len(words)\n",
    "        for i in range(1, n):\n",
    "            if compare(words[i], words[i-1]):\n",
    "                continue\n",
    "            res.append(words[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        res=[words[0]]\n",
    "        n=len(words)\n",
    "\n",
    "        def compare(word1,word2):\n",
    "            freq=[0]*26\n",
    "            for ch in word1:\n",
    "                freq[ord(ch)-ord('a')]+=1\n",
    "            for ch in word2:\n",
    "                freq[ord(ch)-ord('a')]-=1\n",
    "            return all(x==0 for x in freq)\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            if compare(words[i],words[i-1]):\n",
    "                continue\n",
    "            res.append(words[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from collections import defaultdict\n",
    "# class Solution:\n",
    "#     def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "#         dic=defaultdict(list)\n",
    "#         for i,word in enumerate(words):\n",
    "#             key=\"\".join(sorted(word))\n",
    "#             if key not in dic or dic[key] and i!=dic[key][-1]+1:\n",
    "#                 dic[key].append(i) \n",
    "#         lst=[]\n",
    "#         for value in dic.values():\n",
    "#             for v in value:\n",
    "#                 lst.append(v)\n",
    "#         return [word[i] for i,word in enumerate(words) if i in lst]\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        dic=defaultdict(list)\n",
    "        for i,word in enumerate(words):\n",
    "            key=\"\".join(sorted(word))\n",
    "            # if key not in dic or dic[key] and i!=dic[key][-1]+1:\n",
    "            dic[key].append(i)\n",
    "        lst=[]\n",
    "        for value in dic.values():\n",
    "            # tmp=[]\n",
    "            while value:\n",
    "                idx=value.pop()\n",
    "                if not value or value and idx!=value[-1]+1:\n",
    "                    lst.append(idx)\n",
    "        return [word for i,word in enumerate(words) if i in lst]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        from collections import Counter\n",
    "        if not words:\n",
    "            return []\n",
    "\n",
    "        word_stack = []\n",
    "\n",
    "        for word in words:\n",
    "            if not word_stack:\n",
    "                word_stack.append(word)\n",
    "            else:\n",
    "                if Counter(word_stack[-1]) == Counter(word):\n",
    "                    continue\n",
    "                else:\n",
    "                    word_stack.append(word)\n",
    "        return word_stack        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        ans=[words[0]]\n",
    "        for i in words:\n",
    "            a=sorted(list(ans[-1]))\n",
    "            b=sorted(list(i))\n",
    "            if a!=b:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        stack = []\n",
    "        def check(s1, s2):\n",
    "            cnt = Counter(x)\n",
    "            s1 = stack[-1]\n",
    "            cnt1 = Counter(s1)\n",
    "            for k, v in cnt.items():\n",
    "                if cnt1[k] != v:\n",
    "                    return False\n",
    "            for k, v in cnt1.items():\n",
    "                if cnt[k] != v:\n",
    "                    return False\n",
    "            return True\n",
    "        for x in words:\n",
    "            if len(stack):\n",
    "                if check(stack[-1], x):\n",
    "                    pass\n",
    "                else: stack.append(x)\n",
    "            else:\n",
    "                stack.append(x)\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        stack = []\n",
    "        for word in words:\n",
    "            cur = sorted(list(word))\n",
    "            if stack and stack[-1][1] == cur:\n",
    "                continue\n",
    "            else:\n",
    "                stack.append([word, cur[:]])\n",
    "        return [ls[0] for ls in stack]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        r = []\n",
    "        tj = -1\n",
    "        for i in range(len(words)):\n",
    "            if i < tj:\n",
    "                continue\n",
    "            w0 = words[i]\n",
    "            t0 = sorted(w0)\n",
    "            t0 = \"\".join(t0)\n",
    "            r.append(w0)\n",
    "\n",
    "\n",
    "            f = False\n",
    "            for j in range(i+1, len(words)):\n",
    "                w1 = words[j]\n",
    "                t1 = sorted(w1)\n",
    "                t1 = \"\".join(t1)\n",
    "                \n",
    "                if t0 == t1:\n",
    "                    continue\n",
    "                else:\n",
    "                    tj = j\n",
    "                    f = True\n",
    "                    break\n",
    "            if f == False:\n",
    "                tj = len(words)+1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\r\n",
    "        arr = []\r\n",
    "        last = None\r\n",
    "        for s in words:\r\n",
    "            c = Counter(s)\r\n",
    "            if c != last:\r\n",
    "                last = c\r\n",
    "                arr.append(s)\r\n",
    "        return arr\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeAnagrams(self, words: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        n = len(words)\n",
    "        i = 1\n",
    "        while i < n:\n",
    "            # print(sorted(words[i-1]))\n",
    "            # print(sorted(words[i]))\n",
    "            if sorted(words[i-1]) == sorted(words[i]):\n",
    "                words.remove(words[i])\n",
    "                n -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return words"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
